package cn.cxq.learning.single_linked_list;


/**
 * 合并两个排序的链表 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：903102
 * 本题知识点： 链表
 *  算法知识视频讲解
 * 题目描述
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 * 示例1
 * 输入
 * 复制
 * {1,3,5},{2,4,6}
 * 返回值
 * 复制
 * {1,2,3,4,5,6}
 */
public class MergeLinkedList {


    public ListNode Merge(ListNode list1,ListNode list2) {

        ListNode head = new ListNode(Integer.MIN_VALUE); //辅助指针，为了更好写程序逻辑
        ListNode cur = head; //用于生成新链表使用的指针

        while (list1!=null && list2!=null) {
            if (list1.val <list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }

        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }

        return head.next;
    }
}
